//只出现一次的数字
/*给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。*/
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for (auto& num : nums)
            ret ^= num;
        return ret;
    }
};

//只出现一次的数字 III
/*给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。
*/
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        vector<int> ret(2);
        long long sum = 0;
        for (auto& num : nums)
            sum ^= num;
        int f = sum & (-sum);
        int x = 0;
        for (auto& num : nums) {
            if (f & num)
                x ^= num;
        }
        ret[0] = x;
        ret[1] = sum ^ x;
        return ret;
    }
};

//1314. 矩阵区域和
/*给你一个 m x n 的矩阵 mat 和一个整数 k ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和： 

i - k <= r <= i + k, 
j - k <= c <= j + k 且
(r, c) 在矩阵内。*/
class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int n = mat.size();
        int m = mat[0].size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] +
                           mat[i - 1][j - 1];
               // cout << dp[i][j] << " ";
            }
          //  cout << endl;
        }
        //  return dp;
        vector<vector<int>> ret(n, vector<int>(m));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int x1 = max(0, i - k) + 1;
              //  cout << x1 << "-";
                int y1 = max(0, j - k) + 1;
               // cout << y1 << "to";
                int x2 = min(n - 1, i + k) + 1;
               // cout << x2 << "-";
                int y2 = min(m - 1, j + k) + 1;
               // cout << y2 << " ";
                ret[i][j] = dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] +
                            dp[x1 - 1][y1 - 1];
            }
           // cout << endl;
        }
        return ret;
    }
};

//面试题 01.01. 判定字符是否唯一
/*实现一个算法，确定一个字符串 s 的所有字符是否全都不同。*/
class Solution {
public:
    bool isUnique(string astr) {
        if (astr.size() > 26)
            return false;
        int count = 0;
        int temp;
        for (auto& c : astr) {
            temp = c - 'a';
            if (count & (1 << temp))
                return false;
            count |= (1 << temp);
        }
        return true;
    }
};